package day05;

import java.util.Arrays;

//小根堆
public class HeapSort_Min {
    public static void main(String[] args) {
        //[64, 11, 15, 32, 24, 63, 77, 12, 66, 25, -52]
        int[] arr=new int[]{66,77,25,63,15,24,-52,32,64,12,11};
        buildHeap(arr);
        sortHeap(arr);
        reversal(arr);
        System.out.println(Arrays.toString(arr));

    }
    /**
     * 构建堆,堆概念图,入口,从末尾节点的父亲节点
     * */
    public static void buildHeap(int[] arr){
        int startIndex=getParrent(arr.length-1);
        for(int i=startIndex;i>=0;i--){
            minHeap(arr,arr.length,i);
        }

    }

    /**
     * 调整堆,小根堆
     * */
    public static  void minHeap(int[] arr, int heapSize,int index){
        int left=getChildLeft(index);
        int right=getChildRight(index);
        int minIndex=index;//假设当前下标为最小值的下标
        //找到左儿子节点或者右儿子节点中比较小的进行对调
        if(left<heapSize && arr[left]<arr[index]){
            minIndex=left;
        }
        if(right<heapSize &&  arr[right]<arr[minIndex]){
            minIndex=right;
        }
        if(minIndex !=index){
            int temp=arr[index];
            arr[index]=arr[minIndex];
            arr[minIndex]=temp;
            System.out.println("当前索引:"+index);
            System.out.println("和谁对调索引:"+minIndex);
            System.out.println(Arrays.toString(arr));
            minHeap(arr,heapSize,minIndex);
        }

    }


    /**
     * 排序,每次把根节点和当前剩余的末尾节点对调,得到一个从大到小的数组,在进行反转
     */
    public static void sortHeap(int[] arr){
    for(int i=arr.length-1;i>0;i--){
        System.out.println("开始排序::"+i);
        int temp=arr[0];
        arr[0]=arr[i];
        arr[i]=temp;
        //对剩余的数据在排查出最小值放在根节点arr[0]的位置,因为根节点数字发生变化,所以从根节点开始调整
        minHeap(arr,i,0);
    }
    }

    /**
     * 对调
     * @param arr
     */
    public static void reversal(int[] arr){
        for (int i=0;i< arr.length/2;i++)
        {
            int temp=arr[i];
            arr[i]=arr[arr.length-1-i];
            arr[arr.length-1-i]=temp;
        }
    }

    /**
     * 获取当前节点的父节点
     * @param index
     * @return
     */
    public static int getParrent(int index){
        return (index-1)>>1;
//        return (index-1)/2;
    }
    /**
     * 获取当前节点的左子节点
     * @param index
     * @return
     */
    public static int getChildLeft(int index){
        return  (index<<1)+1;
       // return index*2+1;
    }

    /**
     * 获取当前节点的右子节点
     * @param index
     * @return
     */
    public static int getChildRight(int index){
       return  (index<<1)+2;
        // return index*2+2;
    }

}
